The following prior art references are considered by applicants to be the most pertinent to the present invention:
[A] E. R. Berlekamp, "Algebraic Coding Theory," McGraw Hill, pp. 178-199, 1968; PA1 [B] J. L. Massey, "Shift-Register Synthesis and BCH Decoding," IEEE Trans. on IT, IT-15; January 1969; PA1 [C] K. Y. Liu, "Architecture for VLSI Design of Reed-Solomon Decoders," IEEE Trans. on Computers, February 1984, pp. 178-189. PA1 [D] D. L. Whiting, "Bit-Serial Reed-Solomon Decoders in VLSI," PhD thesis, California Institute of Technology, 1984; and PA1 [E] R. T. Chien, "Cyclic Decoding Procedures for BCH Codes," IEEE Trans. on IT-10, pp. 357-363, October 1964.
At p. 184 in reference [A], Berlekamp discloses an algorithm for solving the "key equation" which is the main step in decoding RS codes. As hereafter used in the specification and claims, the term "key equation" is defined as the equation which must be solved to determine the coefficients for the error locator and error evaluation polynomials for a given set of error syndromes. Berlekamp's algorithm, for the simultaneous computation of both error locator and evaluator polynomial coefficients, consists of a computational sequence with one conditional branching condition that divides the sequence into two straight-line sequences, hereafter referred to as the A and B sequences, respectively. The decoding of t symbols in error requires 2t iterations or traversals of this sequence. The A-sequence executes three multiplications and the B-sequence executes five multiplications.
In reference [B], Massey proposed splitting Berlekamp's algorithm by first computing the error location coefficients. These are then used in the computation of the error evaluation polynomials.
Reference [C] describes an implementation of the "Berlekamp-Massey" algorithm disclosed in reference [B]. However, this implementation requires 4t+1 multipliers, 6t registers +t registers for the remaining syndromes and a total of 6t multiplication delays for the computation of error locator and error evaluator polynomials. Furthermore, this reference does not disclose or suggest implementation using bit slice circuits.
In reference [D] at pp. 65 and 104, Whiting noted some arbitrariness in the statement of the conditional branching of Berlekamp's algorithm. Whiting also indicated that a parallel implementation of Berlekamp's algorithm would involve storing twice as many polynomial coefficients and either an additional multiplier or time-multiplexing a single multiplier as compared with the hardware resources required by the parallelization of the algorithm as modified in reference [B].